# 52. N 皇后 II
# n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
# 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
from typing import List


def totalNQueens(n: int) -> int:
    # 棋盘
    n_n = [[0 for _ in range(n)] for _ in range(n)]

    def check_topLeft_topRight(row: int, column: int, chessboard: List[List[int]]) -> bool:
        '''
        检测斜方向上面是否有值
        :param row:
        :param column:
        :param chessboard:
        :return:
        '''
        # 左斜，同一条斜线上面，【行下标-列下标】的值相等
        for i in range(1, row + 1):
            if row - i >= 0 and column - i >= 0 and chessboard[row - i][column - i] == 1:
                return True

        # 右斜，同一条斜线上面，【行下标+列下表】的值相等
        for i in range(1, row + 1):
            if row - i >= 0 and column + i < len(chessboard) and chessboard[row - i][column + i] == 1:
                return True

        return False

    def check_left_top(row: int, column: int, chessboard: List[List[int]]) -> bool:
        '''
        检测横-纵方向上面是否有值
        :param row:
        :param column:
        :param chessboard:
        :return:
        '''
        # 纵向找到一个
        for row_i in range(row - 1, -1, -1):
            if chessboard[row_i][column] == 1:
                return True

        # 横向找到一个
        for column_j in range(column - 1, -1, -1):
            if chessboard[row][column_j] == 1:
                return True

        return False

    def back_track(row: int, max_board: int, chessboard: List[List[int]]) -> int:
        '''
        :param row:
        :param max_board:
        :param chessboard:
        :return:
        '''

        # 小于 max_board 的 row，全部符合条件
        if row == max_board:
            return 1

        temp_re = 0

        for column in range(max_board):
            # 校验当前位置(row,column)在横向，纵向，左斜方向上，右斜方向上是否有冲突
            # True 表示有冲突
            check_conflict = (check_left_top(row, column, chessboard)
                              or check_topLeft_topRight(row, column, chessboard))
            # 有冲突
            if check_conflict:
                continue

            chessboard[row][column] = 1
            row += 1
            temp_re = temp_re + back_track(row, n, chessboard)
            row -= 1
            chessboard[row][column] = 0

        # 返回累计的结果
        return temp_re

    return back_track(0, n, n_n)


result = totalNQueens(1)
print(f"result:{result}")

result = totalNQueens(2)
print(f"result:{result}")

result = totalNQueens(3)
print(f"result:{result}")

result = totalNQueens(4)
print(f"result:{result}")

result = totalNQueens(5)
print(f"result:{result}")

result = totalNQueens(6)
print(f"result:{result}")

result = totalNQueens(7)
print(f"result:{result}")

result = totalNQueens(8)
print(f"result:{result}")

result = totalNQueens(9)
print(f"result:{result}")

result = totalNQueens(10)
print(f"result:{result}")
